Ćwiczenia/4. Ćwiczenia/Zadanie 6. (Znajdowanie największej różnicy sąsiednich liczb w czasie O(n)).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Dana jest tablica $ A $ zawierająca $ n $ parami różnych liczb. Proszę zaproponować algorytm, który znajduje takie dwie liczby $ x $ i $ y $ z $ A $, że $ y − x $ jest jak największa oraz w tablicy nie ma żadnej liczby $ z $ takiej, że $ x < z < y $ (innymi słowy, po posortowaniu tablicy $ A $ rosnąco wynikiem byłyby liczby $ A[i] $ oraz $ A[i+1] $ dla których $ A[i + 1] − A[i] $ jest największe)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Wstępne rozważania"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Oczywiście możliwe jest przesortowanie tablicy, a następnie liniowe przejście i sprawdzanie różnic sąsiednich liczb, ale warto zauważyć, że nie wiemy nic na temat zakresu liczb oraz ich rozkładu. Także nie jest powiedziane, że są to liczby całkowite, więc od razu odrzucamy Radix Sorta i Counting Sorta, które z reguły działają tylko dla zbiorów danych, składających się wyłącznie z liczb całkowitych (lub takich, które można przedstawić jako liczby całkowite - np. ciągi tekstowe). Konwersja liczby zmiennoprzecinkowej na 2 inty, reprezentujące część całkowitą i ułamkową jest w tym przypadku trochę overkill, ale trzeba mieć na uwadze, że w tym przypadku pojawiłby się również błąd, związany z przechowywaniem floatów w pamięci komputera, więc prawdopodobnie byśmy mieli dodatkowe problemy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Po wstępnych rozważaniach widzimy, że jedyny rozsądny algorytm sortowania to Bucket Sort, w którym użylibyśmy rekurencyjnych (lub iteracyjnych) wywołań Bucket Sorta dla dużych wiaderek i Insertion Sorta dla małych. Mimo to, zadanie da się rozwiązać nieco lepiej pod względem złożoności obliczeniowej oraz łatwości wyjaśnienia, że rzeczywista złożoność to $ O(n) $ (w przypadku Bucket Sorta, który nawet korzysta z Bucket Sorta dla dużych wiaderek, prawdopodobne trudno byłoby wybronić rozwiązanie i udowodnić jego poprawność)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Warto zwrócić uwagę, że nie mamy nic powiedzianego o złożoności pamięciowej, więc przyjmujemy, że pamięć nie ma znaczenia. Z tego powodu, możemy zająć nawet $ O(n) $ (lub więcej, jeśli to konieczne) pamięci, ale $ O(n) $ nam wystarczy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Omówienie implementacji"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### 1. krok"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tworzymy $ n $ kubełków tak, aby średnio jedna wartość znalazła się w jednym kubełku (uprości to dalsze postępowanie, jeżeli będzie mało wartości w kubełkach). Skoro mamy $ n $ kubełków, musimy wyznaczyć równomiernie przedział wartości, które mają trafić do danego kubełka. Najłatwiej postąpić podobnie do Bucket Sorta i obliczyć krok, który oznacza rozmiar zakresu wartości (różnicę między górnym a dolnym ograniczeniem przedziału), jako:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    interval = (max_val - min_val) / n  # Dzielimy przez n, bo to liczba wiaderek"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Po stworzeniu kubełków, postępujemy identycznie do Bucket Sorta, a więc przechodzimy liniowo przez tablicę wartości i umieszczamy je kolejno w odpowiednich wiaderkach (kubełkach)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### 2. krok"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Szukamy takich dwóch kubełków, pomiędzy którymi jak największa liczba kubełków jest pusta. Możemy od razu zauważyć, że nie zawsze zdarzy się taka sytuacja i istnieje możliwość, w której wszystkie wartości trafią każda do innego kubełka, więc nie będzie pustych kubełków. Nie jest to jednak problem, o czym powiemy sobie później. Warto również zauważyć, że nigdy nie zdarzy się sytuacja by wszystkie wartości trafiły do jednego kubełka i jednocześnie ten kubełek był jedynym utworzonym kubełkiem, ponieważ zawsze w tablicy muszą być przynajmniej 2 wartości, abyśmy mogli wyznaczyć ich różnicę, a więc liczba kubełków będzie równa przynajmniej 2, bo mamy zależność: $ k = n \\ge 2 $, gdzie $ k $ - liczba kubełków."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Potrzebujemy 2 wskaźników, z których pierwszy przechodzi po tablicy (po kolejnych wiaderkach), a drugi zatrzymuje się na ostatnim niepustym wiaderku różnym od tego, na którym znajduje się pierwszy wskaźnik. Jeżeli pierwszy wskaźnik znajdzie niepuste wiaderko, wówczas wyznaczamy najmniejszą wartość z tego wiaderka oraz wartość największą z poprzedniego niepustego wiaderka i obliczmy ich różnicę. Jeżeli jest ona większa od poprzedniej największej różnicy, zapisujemy wartości $ x $, $ y $ oraz nową największą różnicę. Jeżeli nie, przesuwamy pierwszy wskaźnik na następne wiaderko, a drugi wskaźnik na to wiaderko, na którym poprzednio był pierwszy wskaźnik."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### UWAGA:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zauważmy, że nie jest konieczne rozważanie sytuacji, w której porównujemy wartości dwóch liczb z tego samego wiaderka, ponieważ ZAWSZE najmniejsza wartość trafi do pierwszego wiaderka, a największa do ostatniego utworzonego wiaderka, więc nigdy nie będzie takiej sytuacji, że jeżeli są 2 wartości na granicach przedziału z danego wiaderka, to ich różnica jest największa. Jest to niemożliwe, bo mamy $ n $ wiaderek, więc w takim przypadku przynajmniej jedno wiaderko (jak 2 pewne wartości będą w tym samym wiaderku) musi być puste, a to puste wiaderko NIGDY nie będzie pierwszym ani ostatnim wiaderkiem (to wyjaśniliśmy wyżej). Zatem w takiej sytuacji największą różnicą będzie różnica między najmniejszym elementem z wiaderka na prawo względem pustego wiaderka a największym z wiaderka po lewej stronie pustego wiaderka."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### 3. krok"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Po przejściu wyżej opisaną pętlą po wszystkich wiaderkach, wystarczy zwrócić wyznaczone wartości $ x $ oraz $ y $. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def greatest_difference_neighbors(arr):\n",
    "    # Return None if an array has no more than 1 element\n",
    "    if len(arr) < 2: return None, None\n",
    "    \n",
    "    # Create buckets and calculate the interval\n",
    "    buckets_count = len(arr)\n",
    "    buckets = [[] for _ in range(buckets_count)]\n",
    "    min_val, max_val = minmax(arr)\n",
    "    val_interval = (max_val - min_val) / buckets_count\n",
    "    # Deploy all the values in the correct buckets\n",
    "    for val in arr:\n",
    "        bucket_idx = int((val - min_val) / val_interval - .5)\n",
    "        buckets[bucket_idx].append(val)\n",
    "        \n",
    "    # Look for the greatest neighbours difference\n",
    "    i = 0  # Bucket at index 0 will be never empty\n",
    "    max_diff = 0\n",
    "    x = y = None\n",
    "    for j in range(1, buckets_count):\n",
    "        # If a bucket is not empty, calculate a difference\n",
    "        if buckets[j]:\n",
    "            max_val_i = max(buckets[i])\n",
    "            min_val_j = min(buckets[j])\n",
    "            diff = min_val_j - max_val_i\n",
    "            # Update the max_diff variable if the current difference\n",
    "            # is greater than the previous one\n",
    "            if diff > max_diff:\n",
    "                max_diff = diff\n",
    "                x = max_val_i\n",
    "                y = min_val_j\n",
    "            # Update the i pointer (j will be advanced automatically in\n",
    "            # a for loop)\n",
    "            i = j\n",
    "            \n",
    "    # Return the final results\n",
    "    return x, y\n",
    "            \n",
    "    \n",
    "def minmax(iterable):\n",
    "    # We assume that an iterable supports indexing (to handle sets or dictionaries\n",
    "    # iteration we can use an iterator object but in this example this is overkill).\n",
    "    # Store the last value in order to ease odd-length iterable values comparisons.\n",
    "    max_val = min_val = iterable[-1]  \n",
    "    \n",
    "    for i in range(1, len(iterable), 2):\n",
    "        if iterable[i] > iterable[i-1]:\n",
    "            if iterable[i] > max_val:   max_val = iterable[i]\n",
    "            if iterable[i-1] < min_val: min_val = iterable[i-1]\n",
    "        else:\n",
    "            if iterable[i] < min_val:   min_val = iterable[i]\n",
    "            if iterable[i-1] > max_val: max_val = iterable[i-1]\n",
    "                \n",
    "    # Return the minimum and the maximum value\n",
    "    return min_val, max_val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Funkcja generująca losowe dane wejściowe"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def random_test_data(range_=(-10, 10), vals_count=(0, 20), int_only=False):\n",
    "    if int_only:\n",
    "        arr = [random.randint(*map(int, range_)) for _ in range(random.randint(*vals_count))]\n",
    "    else:\n",
    "        arr = [random.random() * random.randint(*map(int, range_)) for _ in range(random.randint(*vals_count))]\n",
    "    sorted_arr = sorted(arr)\n",
    "    expected_diff = 0\n",
    "    x = y = None\n",
    "    for i in range(1, len(sorted_arr)):\n",
    "        diff = sorted_arr[i] - sorted_arr[i-1]\n",
    "        if diff > expected_diff:\n",
    "            x = sorted_arr[i-1]\n",
    "            y = sorted_arr[i]\n",
    "            expected_diff = diff\n",
    "    return arr, sorted_arr, expected_diff, x, y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Kod sprawdzający poprawność algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Result:   x = -4.761466021489896, y = 17.076449072191423\n",
      "Expected: x = -4.761466021489896, y = 17.076449072191423\n",
      "Result difference:   21.837915093681318\n",
      "Expected difference: 21.837915093681318\n",
      "An algorithm is CORRECT\n",
      "\n",
      "Input array:\n",
      "[17.076449072191423, -11.249705368186314, -34.85072202867098, 19.5644339182881, -19.430198445675163, 21.438538669436152, -4.761466021489896, 17.17855164119556, -14.809660698537623]\n",
      "\n",
      "Sorted array:\n",
      "[-34.85072202867098, -19.430198445675163, -14.809660698537623, -11.249705368186314, -4.761466021489896, 17.076449072191423, 17.17855164119556, 19.5644339182881, 21.438538669436152]\n"
     ]
    }
   ],
   "source": [
    "arr, sorted_arr, expected_diff, expected_x, expected_y = random_test_data(\n",
    "    range_=(-100, 100), \n",
    "    vals_count=(0, 100),\n",
    "    int_only=False\n",
    ")\n",
    "\n",
    "x, y = greatest_difference_neighbors(arr)\n",
    "diff = (y - x) if x and y else None\n",
    "\n",
    "print(f\"Result:   x = {x}, y = {y}\")\n",
    "print(f\"Expected: x = {expected_x}, y = {expected_y}\")\n",
    "print(f\"Result difference:   {diff}\")\n",
    "print(f\"Expected difference: {expected_diff}\")\n",
    "print(f\"An algorithm is {'CORRECT' if x == expected_x and y == expected_y else 'WRONG'}\")\n",
    "print(\"\\nInput array:\", arr, sep='\\n')\n",
    "print(\"\\nSorted array:\", sorted_arr, sep='\\n')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}